home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Utilities / byacc 1.8.2 / lr0.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-04  |  10.1 KB  |  616 lines  |  [TEXT/R*ch]
  1. #include "defs.h"
  2.  
  3. extern short *itemset;
  4. extern short *itemsetend;
  5. extern unsigned *ruleset;
  6.  
  7. int nstates;
  8. core *first_state;
  9. shifts *first_shift;
  10. reductions *first_reduction;
  11.  
  12. static core **state_set;
  13. static core *this_state;
  14. static core *last_state;
  15. static shifts *last_shift;
  16. static reductions *last_reduction;
  17.  
  18. static int nshifts;
  19. static short *shift_symbol;
  20.  
  21. static short *redset;
  22. static short *shiftset;
  23.  
  24. static short **kernel_base;
  25. static short **kernel_end;
  26. static short *kernel_items;
  27.  
  28. static void allocate_itemsets _P_((void));
  29. static void allocate_storage _P_((void));
  30. static void append_states _P_((void));
  31. static void free_storage _P_((void));
  32. static void generate_states _P_((void));
  33. static int get_state _P_((int symbol));
  34. static void initialize_states _P_((void));
  35. static void new_itemsets _P_((void));
  36. static core *new_state _P_((int symbol));
  37. static void save_shifts _P_((void));
  38. static void save_reductions _P_((void));
  39. static void set_derives _P_((void));
  40. static void set_nullable _P_((void));
  41.  
  42. #ifdef DEBUG
  43. extern void print_derives _P_((void));
  44. extern void show_cores _P_((void));
  45. extern void show_ritems _P_((void));
  46. extern void show_rrhs _P_((void));
  47. extern void show_shifts _P_((void));
  48. #endif
  49.  
  50. static void allocate_itemsets()
  51. {
  52.     register short *itemp;
  53.     register short *item_end;
  54.     register int symbol;
  55.     register int i;
  56.     register int count;
  57.     register int max;
  58.     register short *symbol_count;
  59.  
  60.     count = 0;
  61.     symbol_count = NEW2(nsyms, short);
  62.  
  63.     item_end = ritem + nitems;
  64.     for (itemp = ritem; itemp < item_end; itemp++)
  65.     {
  66.     symbol = *itemp;
  67.     if (symbol >= 0)
  68.     {
  69.         count++;
  70.         symbol_count[symbol]++;
  71.     }
  72.     }
  73.  
  74.     kernel_base = NEW2(nsyms, short *);
  75.     kernel_items = NEW2(count, short);
  76.  
  77.     count = 0;
  78.     max = 0;
  79.     for (i = 0; i < nsyms; i++)
  80.     {
  81.     kernel_base[i] = kernel_items + count;
  82.     count += symbol_count[i];
  83.     if (max < symbol_count[i])
  84.         max = symbol_count[i];
  85.     }
  86.  
  87.     shift_symbol = symbol_count;
  88.     kernel_end = NEW2(nsyms, short *);
  89. }
  90.  
  91.  
  92. static void allocate_storage()
  93. {
  94.     allocate_itemsets();
  95.     shiftset = NEW2(nsyms, short);
  96.     redset = NEW2(nrules + 1, short);
  97.     state_set = NEW2(nitems, core *);
  98. }
  99.  
  100.  
  101. static void append_states()
  102. {
  103.     register int i;
  104.     register int j;
  105.     register int symbol;
  106.  
  107. #ifdef    TRACE
  108.     fprintf(stderr, "Entering append_states()\n");
  109. #endif
  110.     for (i = 1; i < nshifts; i++)
  111.     {
  112.     symbol = shift_symbol[i];
  113.     j = i;
  114.     while (j > 0 && shift_symbol[j - 1] > symbol)
  115.     {
  116.         shift_symbol[j] = shift_symbol[j - 1];
  117.         j--;
  118.     }
  119.     shift_symbol[j] = symbol;
  120.     }
  121.  
  122.     for (i = 0; i < nshifts; i++)
  123.     {
  124.     symbol = shift_symbol[i];
  125.     shiftset[i] = get_state(symbol);
  126.     }
  127. }
  128.  
  129.  
  130. static void free_storage()
  131. {
  132.     FREE(shift_symbol);
  133.     FREE(redset);
  134.     FREE(shiftset);
  135.     FREE(kernel_base);
  136.     FREE(kernel_end);
  137.     FREE(kernel_items);
  138.     FREE(state_set);
  139. }
  140.  
  141.  
  142.  
  143. static void generate_states()
  144. {
  145.     allocate_storage();
  146.     itemset = NEW2(nitems, short);
  147.     ruleset = NEW2(WORDSIZE(nrules), unsigned);
  148.     set_first_derives();
  149.     initialize_states();
  150.  
  151.     while (this_state)
  152.     {
  153.     closure(this_state->items, this_state->nitems);
  154.     save_reductions();
  155.     new_itemsets();
  156.     append_states();
  157.  
  158.     if (nshifts > 0)
  159.         save_shifts();
  160.  
  161.     this_state = this_state->next;
  162.     }
  163.  
  164.     finalize_closure();
  165.     free_storage();
  166. }
  167.  
  168.  
  169.  
  170. static int get_state(symbol)
  171. int symbol;
  172. {
  173.     register int key;
  174.     register short *isp1;
  175.     register short *isp2;
  176.     register short *iend;
  177.     register core *sp;
  178.     register int found;
  179.     register int n;
  180.  
  181. #ifdef    TRACE
  182.     fprintf(stderr, "Entering get_state(%d)\n", symbol);
  183. #endif
  184.  
  185.     isp1 = kernel_base[symbol];
  186.     iend = kernel_end[symbol];
  187.     n = iend - isp1;
  188.  
  189.     key = *isp1;
  190.     assert(0 <= key && key < nitems);
  191.     sp = state_set[key];
  192.     if (sp)
  193.     {
  194.     found = 0;
  195.     while (!found)
  196.     {
  197.         if (sp->nitems == n)
  198.         {
  199.         found = 1;
  200.         isp1 = kernel_base[symbol];
  201.         isp2 = sp->items;
  202.  
  203.         while (found && isp1 < iend)
  204.         {
  205.             if (*isp1++ != *isp2++)
  206.             found = 0;
  207.         }
  208.         }
  209.  
  210.         if (!found)
  211.         {
  212.         if (sp->link)
  213.         {
  214.             sp = sp->link;
  215.         }
  216.         else
  217.         {
  218.             sp = sp->link = new_state(symbol);
  219.             found = 1;
  220.         }
  221.         }
  222.     }
  223.     }
  224.     else
  225.     {
  226.     state_set[key] = sp = new_state(symbol);
  227.     }
  228.  
  229.     return (sp->number);
  230. }
  231.  
  232.  
  233.  
  234. static void initialize_states()
  235. {
  236.     register int i;
  237.     register short *start_derives;
  238.     register core *p;
  239.  
  240.     start_derives = derives[start_symbol];
  241.     for (i = 0; start_derives[i] >= 0; ++i)
  242.     continue;
  243.  
  244.     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
  245.  
  246.     p->next = 0;
  247.     p->link = 0;
  248.     p->number = 0;
  249.     p->accessing_symbol = 0;
  250.     p->nitems = i;
  251.  
  252.     for (i = 0;     start_derives[i] >= 0; ++i)
  253.     p->items[i] = rrhs[start_derives[i]];
  254.  
  255.     first_state = last_state = this_state = p;
  256.     nstates = 1;
  257. }
  258.  
  259.  
  260. static void new_itemsets()
  261. {
  262.     register int i;
  263.     register int shiftcount;
  264.     register short *isp;
  265.     register short *ksp;
  266.     register int symbol;
  267.  
  268.     for (i = 0; i < nsyms; i++)
  269.     kernel_end[i] = 0;
  270.  
  271.     shiftcount = 0;
  272.     isp = itemset;
  273.     while (isp < itemsetend)
  274.     {
  275.     i = *isp++;
  276.     symbol = ritem[i];
  277.     if (symbol > 0)
  278.     {
  279.         ksp = kernel_end[symbol];
  280.         if (!ksp)
  281.         {
  282.         shift_symbol[shiftcount++] = symbol;
  283.         ksp = kernel_base[symbol];
  284.         }
  285.  
  286.         *ksp++ = i + 1;
  287.         kernel_end[symbol] = ksp;
  288.     }
  289.     }
  290.  
  291.     nshifts = shiftcount;
  292. }
  293.  
  294.  
  295.  
  296. static core *new_state(symbol)
  297. int symbol;
  298. {
  299.     register int n;
  300.     register core *p;
  301.     register short *isp1;
  302.     register short *isp2;
  303.     register short *iend;
  304.  
  305. #ifdef    TRACE
  306.     fprintf(stderr, "Entering new_state(%d)\n", symbol);
  307. #endif
  308.  
  309.     if (nstates >= MAXSHORT)
  310.     fatal("too many states");
  311.  
  312.     isp1 = kernel_base[symbol];
  313.     iend = kernel_end[symbol];
  314.     n = iend - isp1;
  315.  
  316.     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  317.     p->accessing_symbol = symbol;
  318.     p->number = nstates;
  319.     p->nitems = n;
  320.  
  321.     isp2 = p->items;
  322.     while (isp1 < iend)
  323.     *isp2++ = *isp1++;
  324.  
  325.     last_state->next = p;
  326.     last_state = p;
  327.  
  328.     nstates++;
  329.  
  330.     return (p);
  331. }
  332.  
  333.  
  334. #ifdef DEBUG
  335.  
  336. void show_cores()
  337. {
  338.     core *p;
  339.     int i, j, k, n;
  340.     int itemno;
  341.  
  342.     k = 0;
  343.     for (p = first_state; p; ++k, p = p->next)
  344.     {
  345.     if (k) printf("\n");
  346.     printf("state %d, number = %d, accessing symbol = %s\n",
  347.         k, p->number, symbol_name[p->accessing_symbol]);
  348.     n = p->nitems;
  349.     for (i = 0; i < n; ++i)
  350.     {
  351.         itemno = p->items[i];
  352.         printf("%4d  ", itemno);
  353.         j = itemno;
  354.         while (ritem[j] >= 0) ++j;
  355.         printf("%s :", symbol_name[rlhs[-ritem[j]]]);
  356.         j = rrhs[-ritem[j]];
  357.         while (j < itemno)
  358.         printf(" %s", symbol_name[ritem[j++]]);
  359.         printf(" .");
  360.         while (ritem[j] >= 0)
  361.         printf(" %s", symbol_name[ritem[j++]]);
  362.         printf("\n");
  363.         fflush(stdout);
  364.     }
  365.     }
  366. }
  367.  
  368.  
  369. void show_ritems()
  370. {
  371.     int i;
  372.  
  373.     for (i = 0; i < nitems; ++i)
  374.     printf("ritem[%d] = %d\n", i, ritem[i]);
  375. }
  376.  
  377.  
  378. void show_rrhs()
  379. {
  380.     int i;
  381.  
  382.     for (i = 0; i < nrules; ++i)
  383.     printf("rrhs[%d] = %d\n", i, rrhs[i]);
  384. }
  385.  
  386.  
  387. void show_shifts()
  388. {
  389.     shifts *p;
  390.     int i, j, k;
  391.  
  392.     k = 0;
  393.     for (p = first_shift; p; ++k, p = p->next)
  394.     {
  395.     if (k) printf("\n");
  396.     printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  397.         p->nshifts);
  398.     j = p->nshifts;
  399.     for (i = 0; i < j; ++i)
  400.         printf("\t%d\n", p->shift[i]);
  401.     }
  402. }
  403. #endif
  404.  
  405.  
  406. static void save_shifts()
  407. {
  408.     register shifts *p;
  409.     register short *sp1;
  410.     register short *sp2;
  411.     register short *send;
  412.  
  413.     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  414.             (nshifts - 1) * sizeof(short)));
  415.  
  416.     p->number = this_state->number;
  417.     p->nshifts = nshifts;
  418.  
  419.     sp1 = shiftset;
  420.     sp2 = p->shift;
  421.     send = shiftset + nshifts;
  422.  
  423.     while (sp1 < send)
  424.     *sp2++ = *sp1++;
  425.  
  426.     if (last_shift)
  427.     {
  428.     last_shift->next = p;
  429.     last_shift = p;
  430.     }
  431.     else
  432.     {
  433.     first_shift = p;
  434.     last_shift = p;
  435.     }
  436. }
  437.  
  438.  
  439.  
  440. static void save_reductions()
  441. {
  442.     register short *isp;
  443.     register short *rp1;
  444.     register short *rp2;
  445.     register int item;
  446.     register int count;
  447.     register reductions *p;
  448.     register short *rend;
  449.  
  450.     count = 0;
  451.     for (isp = itemset; isp < itemsetend; isp++)
  452.     {
  453.     item = ritem[*isp];
  454.     if (item < 0)
  455.     {
  456.         redset[count++] = -item;
  457.     }
  458.     }
  459.  
  460.     if (count)
  461.     {
  462.     p = (reductions *) allocate((unsigned) (sizeof(reductions) +
  463.                     (count - 1) * sizeof(short)));
  464.  
  465.     p->number = this_state->number;
  466.     p->nreds = count;
  467.  
  468.     rp1 = redset;
  469.     rp2 = p->rules;
  470.     rend = rp1 + count;
  471.  
  472.     while (rp1 < rend)
  473.         *rp2++ = *rp1++;
  474.  
  475.     if (last_reduction)
  476.     {
  477.         last_reduction->next = p;
  478.         last_reduction = p;
  479.     }
  480.     else
  481.     {
  482.         first_reduction = p;
  483.         last_reduction = p;
  484.     }
  485.     }
  486. }
  487.  
  488.  
  489. static void set_derives()
  490. {
  491.     register int i, k;
  492.     register int lhs;
  493.     register short *rules;
  494.  
  495.     derives = NEW2(nsyms, short *);
  496.     rules = NEW2(nvars + nrules, short);
  497.  
  498.     k = 0;
  499.     for (lhs = start_symbol; lhs < nsyms; lhs++)
  500.     {
  501.     derives[lhs] = rules + k;
  502.     for (i = 0; i < nrules; i++)
  503.     {
  504.         if (rlhs[i] == lhs)
  505.         {
  506.         rules[k] = i;
  507.         k++;
  508.         }
  509.     }
  510.     rules[k] = -1;
  511.     k++;
  512.     }
  513.  
  514. #ifdef    DEBUG
  515.     print_derives();
  516. #endif
  517. }
  518.  
  519. #if __STDC__
  520. void free_derives(void)
  521. #else
  522. void free_derives()
  523. #endif
  524. {
  525.     FREE(derives[start_symbol]);
  526.     FREE(derives);
  527. }
  528.  
  529. #ifdef    DEBUG
  530. static void print_derives()
  531. {
  532.     register int i;
  533.     register short *sp;
  534.  
  535.     printf("\nDERIVES\n\n");
  536.  
  537.     for (i = start_symbol; i < nsyms; i++)
  538.     {
  539.     printf("%s derives ", symbol_name[i]);
  540.     for (sp = derives[i]; *sp >= 0; sp++)
  541.     {
  542.         printf("  %d", *sp);
  543.     }
  544.     putchar('\n');
  545.     }
  546.  
  547.     putchar('\n');
  548. }
  549. #endif
  550.  
  551.  
  552. static void set_nullable()
  553. {
  554.     register int i, j;
  555.     register int empty;
  556.     int done;
  557.  
  558.     nullable = MALLOC(nsyms);
  559.  
  560.     for (i = 0; i < nsyms; ++i)
  561.     nullable[i] = 0;
  562.  
  563.     done = 0;
  564.     while (!done)
  565.     {
  566.     done = 1;
  567.     for (i = 1; i < nitems; i++)
  568.     {
  569.         empty = 1;
  570.         while ((j = ritem[i]) >= 0)
  571.         {
  572.         if (!nullable[j])
  573.             empty = 0;
  574.         ++i;
  575.         }
  576.         if (empty)
  577.         {
  578.         j = rlhs[-j];
  579.         if (!nullable[j])
  580.         {
  581.             nullable[j] = 1;
  582.             done = 0;
  583.         }
  584.         }
  585.     }
  586.     }
  587.  
  588. #ifdef DEBUG
  589.     for (i = 0; i < nsyms; i++)
  590.     {
  591.     if (nullable[i])
  592.         printf("%s is nullable\n", symbol_name[i]);
  593.     else
  594.         printf("%s is not nullable\n", symbol_name[i]);
  595.     }
  596. #endif
  597. }
  598.  
  599.  
  600. #if __STDC__
  601. void free_nullable(void)
  602. #else
  603. void free_nullable()
  604. #endif
  605. {
  606.     FREE(nullable);
  607. }
  608.  
  609.  
  610. void lr0()
  611. {
  612.     set_derives();
  613.     set_nullable();
  614.     generate_states();
  615. }
  616.